package com.cloudjan.leetcod.常见算法技巧;

/**
 * 二分查找
 * 又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置
 * 的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，
 * 则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。
 */
public class 二分查找 {

    /**
     * 时间复杂度O(lgn)
     * 查找a在数组array中的位置返回下标，没有返回-1
     * @param array
     * @param a
     * @return
     */
    public static int binarySearch(int[] array,int a){
        int l = 0; //左指针
        int r = array.length - 1; //右指针
        while(l<=r){
            int mid = l + (r - l) / 2;
            if(a>mid){ //a在右半部分
                l = mid + 1;
            }else if(a<mid){//a在左半部分
                r = mid - 1;
            }else {//a等于mid直接返回
                return mid;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] array = {0,1,2,3,4,5,6};
        System.out.println(binarySearch(array, 3));
    }

}
